package dp;

/**
 * @Author: wangliuyang
 * @Date: 2021/6/8 17:38
 * @Description: 求字符串最长公共子序列
 */
public class LCS {
    public static int CLS(String s1, String s2) {
        int max = 0;
        if (s1 == null || s2 == null) {
            return max;
        }
        int[][] dp = new int[s1.length() + 1][s2.length() + 1];
        char[] chars1 = s1.toCharArray();
        char[] chars2 = s2.toCharArray();
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[i].length; j++) {
                dp[i][j] = chars1[i - 1] == chars2[j - 1] ? dp[i - 1][j - 1] + 1 : Math.max(dp[i][j-1],dp[i-1][j]);
            }
        }
        max = dp[dp.length - 1][dp[1].length - 1];
        return max;
    }

    public static void main(String[] args) {

    }
}
